這道題主要是判斷一個整數是否是回文數字。回文數字是指正著讀和反著讀都相同的數字。

題目：
給定一個整數 x，判斷它是否是回文數字。如果一個數字是負數，它不會是回文數字。例如，-121 不是回文數字，因為反過來後是 121-。如果一個正數是回文數字，那麼它正向和反向的數字排列應該相同。

範例：

輸入: 121
輸出: true

輸入: -121
輸出: false

輸入: 10
輸出: false

解題思路

解法1：整個數字反轉

回文的話反轉後跟原本數字應該相同，

reverse 改用 long，是因為考慮到有很大的數字會乘法溢位，例如 x = 1234567899，

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;

        int num = x;
        long reverse = 0;
        while (num != 0) {
            int digit = num % 10;
            reverse = reverse * 10 + digit;
            num = num / 10;
        }

        if (reverse == x)
            return true;
        else
            return false;
    }
};

時間複雜度：O(log n)，因為每次迴圈減少一個十進位數字。
空間複雜度：O(1)

解法2：stack 先進後出特性

用 stack 先進後出特性，然後藉此判斷是否為回文，

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;

        int num = x;
        stack<int> stk;
        while (num != 0) {
            stk.push(num % 10);
            num = num / 10;
        }

        num = x;
        while (num != 0) {
            if (stk.top() != num % 10)
                return false;
            stk.pop();
            num = num / 10;
        }

        return true;
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

解法3 只反轉一半

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;
        
        int num = x;
        long reversedHalf = 0;
        while (num > reversedHalf) {
            int digit = num % 10;
            reversedHalf = reversedHalf * 10 + digit;
            num = num / 10;
        }

        if (num == reversedHalf || num == reversedHalf / 10)
            return true;
        else
            return false;
    }
};

時間複雜度：O(log n)，因為每次迴圈減少一個十進位數字。
空間複雜度：O(1)

參考：
#9. Palindrome Number